The engineering and business requirements of navigation processors in wireless client-server (WCS) navigators, in which route searches are performed at a central location then transmitted to mobile units, differ somewhat from those of standard standalone navigators. One major difference is that WCS navigation processors receive very frequent route requests from many handsets whereas standard navigators typically receive one request every few hours. Thus, in order to minimize infrastructure costs, it is important to time-optimize route generation methods.
FIG. 1 is a simplified illustration of a typical routing problem. A person at point A wishes to travel to a destination at point B. The function of a route generator is to determine a series of movements that will allow the person to reach his destination. In the parlance of artificial intelligence, the map is represented as a set of nodes (intersections) and paths between them (roads). A generic search for a route can be represented by a diagram in which each choice of path is represented by a line leading to a new choice. FIG. 2 gives an example of the start of a search diagram of a route search from A to B.
As can be seen from the figures, the number of possibilities that must be considered by routing algorithm grows very quickly with the number of nodes and paths in a map. This process can be made much more efficient with the addition of heuristics (rules), such as “don't return to the node you just came from,” or “follow a path roughly in the direction of the destination,” or by using depth-first search or cost heuristics, all of which are well-known and described in artificial intelligence literature. Nevertheless, as the size of a map increases, the computing time, memory, and computing power required to compute a route also increase dramatically. Given the constraints of running a WCS navigation server, it is beneficial to use a method of route generation that first simplifies the map.